package Sequence;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0040 {
}

class Solution0040_1 {
    List<List<Integer>> ans = new ArrayList<>();
    int[] candidates;
    int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;

        backtrack(0, new ArrayList<>(), 0);
        return ans;
    }

    public boolean backtrack(int sum, ArrayList<Integer> record,int index) {
        if (sum==target) ans.add(new ArrayList<>(record));
        if(sum>=target||index>=candidates.length) return false;

        for (; index < candidates.length; index=next(index)) {
            int candidate = candidates[index];

            record.add(candidate);
            boolean flag = backtrack(sum + candidate, record, index + 1);
            record.remove(record.size()-1);
            if(!flag) break;
        }

        return true;
    }

    public int next(int index){
        int candidate = candidates[index];

        for (;index<candidates.length;index++)
            if (candidates[index]!=candidate) break;

        return index;
    }

}
